package com.masterlu.leetcode.daily.stack.simple;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 下一个更大元素 I
 * https://leetcode-cn.com/problems/next-greater-element-i/
 *
 * @Author：masterlu
 * @Date：2021/4/28 9:32 上午
 */
public class S496NextGreaterElement {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        int[] result = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();

        //1.计算nums2右侧最大值，并将结果存储在map中.（主要逻辑）
        for (int i : nums2) {
            if (stack.isEmpty() || stack.peek() > i) {
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty() && stack.peek() < i){
                map.put(stack.pop(), i);
            }
            stack.push(i);
        }
        //2.对右侧没有最大值数据进行处理
        while (!stack.isEmpty()) {
            map.put(stack.pop(), -1);
        }

        //循环nums1数组，统计数据
        for (int i = 0; i < result.length; i++) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }

}
